# https://blog.csdn.net/CQZHOUZR/article/details/121978928

import copy
from 阵势 import *

上,下,左,右=0,2,3,1
#D={0:"上",2:"下",3:"左",1:"右",}

class node:
    def __init__(self):
        self.board= copy.deepcopy(场地初始状态)
        self.chess_game=[]
        self.当前移动=0
        self.移动队列=[]  #存储该chess_game所有的可能下一步
        self.parent=None  #双亲
    
    def 对称(self): #计算chess_game的左右对称的chess_game
        t=copy.deepcopy(self.board)
        for i in range(1,6):
            for j in (1,3):
                t[i][j],t[i][5-j]=t[i][5-j],t[i][j]
        return t    
                       
    def print_board(self):
        for 行 in self.board:
            for 形状 in 行:
                if 形状 == 1:
                    print('口', end='')
                elif 形状 == 2:
                    print('羽', end='')
                elif 形状 == 3:
                    print('纵', end='')
                elif 形状 == 4:
                    print('操', end='')
                elif 形状 == 5:
                    print('卒', end='')
                elif 形状 == 0:
                    print('〇', end='')
            print()

    def 更新棋子占据位置(self,棋子):
        z=棋子.形状
        x=棋子.坐标[0]+1
        y=棋子.坐标[1]+1        
        if 棋子.形状==3:
            self.board[x][y]=棋子.形状
            self.board[x+1][y]=棋子.形状
        elif 棋子.形状==4:
            self.board[x][y]=棋子.形状
            self.board[x+1][y]=棋子.形状
            self.board[x][y+1]=棋子.形状
            self.board[x+1][y+1]=棋子.形状
        elif 棋子.形状==2:
            self.board[x][y]=棋子.形状
            self.board[x][y+1]=棋子.形状
        else:
            self.board[x][y]=棋子.形状
 
    def 更新棋盘占据位置(self):
        self.board= copy.deepcopy(场地初始状态)
        for x in self.chess_game:
            self.更新棋子占据位置(x)        
 
    def 更新棋子移动性(self,棋子):
        x=棋子.坐标[0]+1
        y=棋子.坐标[1]+1
        棋子.可走方向=[0,0,0,0]
        if 棋子.形状==3:
            if self.board[x][y-1]==0 and self.board[x+1][y-1]==0:   
                棋子.可走方向[左]=1  
            if self.board[x-1][y]==0:                               
                棋子.可走方向[上]=1   
            if self.board[x+2][y]==0:                               
                棋子.可走方向[下]=1   
            if self.board[x][y+1]==0 and self.board[x+1][y+1]==0:   
                棋子.可走方向[右]=1   
        elif 棋子.形状==4:
            if self.board[x][y-1]==0 and self.board[x+1][y-1]==0:
                棋子.可走方向[左]=1  
            if self.board[x-1][y]==0 and self.board[x-1][y+1]==0:
                棋子.可走方向[上]=1   
            if self.board[x+2][y]==0 and self.board[x+2][y+1]==0:
                棋子.可走方向[下]=1   
            if self.board[x][y+2]==0 and self.board[x+1][y+2]==0:
                棋子.可走方向[右]=1   
        elif 棋子.形状==2:
            if self.board[x][y-1]==0 :
                棋子.可走方向[左]=1  
            if self.board[x-1][y]==0 and self.board[x-1][y+1]==0:
                棋子.可走方向[上]=1   
            if self.board[x+1][y]==0 and self.board[x+1][y+1]==0:
                棋子.可走方向[下]=1   
            if self.board[x][y+2]==0:
                棋子.可走方向[右]=1   
        else:
            if self.board[x][y-1]==0 :
                棋子.可走方向[左]=1  
            if self.board[x-1][y]==0 :
                棋子.可走方向[上]=1   
            if self.board[x+1][y]==0:
                棋子.可走方向[下]=1   
            if self.board[x][y+1]==0:
                棋子.可走方向[右]=1   
        if sum(棋子.可走方向)>0:
            棋子.可动=True
    def 更新棋盘移动性(self):
        for x in self.chess_game:
            self.更新棋子移动性(x)
    def 生成移动队列(self):
        self.移动队列=[]
        self.当前移动=0
        for x in self.chess_game:
            if x.可动:
                for i in range(4):
                    if x.可走方向[i]==1:
                        self.移动队列.append([i,x.名称])        
               
    def 移动棋子(self,x):        
        for i in self.chess_game:
            if i.名称!=x[1]:
                continue
            if x[0]==上:
                i.坐标[0]-=1  
            elif x[0]==下:
                i.坐标[0]+=1  
            elif x[0]==左:
                i.坐标[1]-=1  
            elif x[0]==右:
                i.坐标[1]+=1  
    def 成功(self):
        for i in self.chess_game:
            if i.名称=="曹操":
                if i.坐标[0]==3 and i.坐标[1]==1:                
                    return True
                if i.坐标[0]==2 and i.坐标[1]==1:
                    if self.board[4+1][1+1]==0 and self.board[4+1][2+1]==0:
                        return True
                if i.坐标[0]==3 and i.坐标[1]==0:
                    if self.board[3+1][2+1]==0 and self.board[4+1][2+1]==0:
                        return True
                if i.坐标[0]==3 and i.坐标[1]==2:
                    if self.board[3+1][1+1]==0 and self.board[4+1][1+1]==0:
                        return True
        return False
 
#初始化
已产生棋局的位示图=[]
棋局队列=[]   
根节点=node()

根节点.chess_game.append(曹操)
根节点.chess_game.append(马超)
根节点.chess_game.append(黄忠)
根节点.chess_game.append(张飞)
根节点.chess_game.append(赵云)
根节点.chess_game.append(关羽)
根节点.chess_game.append(卒1)
根节点.chess_game.append(卒2)
根节点.chess_game.append(卒3)
根节点.chess_game.append(卒4)
        
根节点.更新棋盘占据位置()
根节点.更新棋盘移动性()
根节点.生成移动队列()
已产生棋局的位示图.append(根节点.board) 
棋局队列.append(根节点) #根节点入队列
  
while True:    
    while True:
        if 棋局队列[0].当前移动>=len(棋局队列[0].移动队列):
            #队首节点的全部孩子已入队列，将其移出队列            
            棋局队列.pop(0)  #队首节点出队列 
            #该节点仍然在内存中，可通过其孩子节点的双亲指针访问到
            continue
        节点=copy.deepcopy(棋局队列[0])
        节点.移动棋子(节点.移动队列[节点.当前移动])
        棋局队列[0].当前移动+=1    
        节点.更新棋盘占据位置()
        if 节点.board in 已产生棋局的位示图:             
            continue
        elif 节点.对称() in 已产生棋局的位示图:            
            continue
            #break
        else:        
            break  
    
    节点.更新棋盘移动性()    
    节点.生成移动队列()
    节点.parent=棋局队列[0] #记录该节点的双亲节点
    已产生棋局的位示图.append(节点.board)    
    
    if 节点.成功():
        count=0
        print("成功")
        节点.print_board()
        print("-----------------------")
        while True:
            if 节点.parent: #从结果节点沿双亲指针打印出全部移动步骤
                count+=1
                节点=节点.parent
                节点.print_board()
                print("-----------------------")
            else:
                break
        print("步数：{}".format(count))        
        break
    else:
        棋局队列.append(节点)    #入队列
 
 